分布式系统的“流言蜚语”

点击上方 "程序员小乐" ，关注公众号

8点20分，第一时间与你相约

每日英文 

The best way to escape from the past is not to avoid or forget it, but to accept and forgive it. 

摆脱过去并不是逃避或者忘记，只是学着去承受和宽恕。

小乐有话说 

不管真的假的，能看清就是幸运的。不管苦的乐的，有未来就难得。

来自公众号：码农翻身

封面来自网络

00 前言 

你也许用过Redis，Cassandra，Amazon S3, BitTorrent 等著名的软件，但是也许你不知道，它们在底层通信时都采用了一个叫做Gossip（流言蜚语）的协议。

我一直以来都想写一下这个Gossip， 但是苦于找不到合适的方式，今天看到这Gossip模拟器（点阅读原文查看），我就知道不用我写了，我给大家搬运一下就行了。

开始之前，我的习惯还是得先讲讲问题，有了问题，你才会知道这个技术到底想解决什么问题。

假设你有一个集群，这个集群中有上千台服务器，现在客户对服务器A上的一个数据做了改动，你想让这个改动迅速地传遍整个集群中的服务器，换句话说，让这些服务器的数据都达到一致性的状态， 你会怎么办呢？

01 最简单的办法 

让客户的数据改动，保存到一个稳定的服务器X上，然后其他的服务器A,B,C,D.... 都从服务器X中去定期地拉取数据不就行了？

但是在分布式的情况下，至少会有两个问题：

1.  服务器X虽然很稳定，但还是可能会挂掉，一旦挂掉，整个系统就完了。

还可以给服务器X做备份嘛，让数据同步到服务器X1, X2,X3....中，这样就不怕服务器X挂掉了，但是问题又出现了，如何让数据在这些服务器X, X1,X2,X3之间达成一致呢？

2.  由于网络原因（这是非常常见的），如果某一台服务器H连不上服务器X， 它也无法拉取数据了，即使服务器H能连上其他服务器也不行。

这就是一个典型的分布式系统中的一致性的问题，科学家们已经研究出了很多中算法出来，比如Paxos, Raft，今天我们要介绍的就是其中之一：Gossip协议，也可以叫做流言蜚语协议，这个协议就类似于社交网络中小道消息的传播，一传十，十传百，最后迅速传遍整个网络。

02 图解Gossip 

流言蜚语协议是怎么玩的呢？ 我们来看看这个图：

图中有40个花花绿绿的圆圈，表示40个节点，就认为是服务器吧。

接下来，我选择了一个节点，假设数据改动发生在它这里：

接下里我可以显示这个节点所知道的那些“相邻节点”,  如图中的绿线所示。

其中有4根线比较粗，那就意味着这个节点从相邻节点中随机地选择了4个来发送消息。

数目4 被称为Fanout

接下里就可以发送消息了，注意，消息发送完以后，这4个节点也变红了，这就意味着他们已经收到了数据的更新。

用病毒传播的术语来说，有4个节点被感染了。

接下来，所有的红色节点（拥有数据更新的、被“感染”的节点）遵循第一个节点的策略，从自己知道的节点中随机选择4个，传播这次的数据改动。

于是，更多的节点被“感染”了，变红了。

如此循环下去，被感染的节点持续随机传播“病毒”（数据改动），最后所有的节点都被传染了，达到了一致性的状态。

来一张动图，看一看整体的过程，感兴趣的同学可以直接点击阅读原文去网站玩一下，非常有意思。

这里展示的是40个节点的情况，可以看到，经过3轮次以后，所有的节点都被感染了，数据保持一致了。

03 优点 

1. 可伸缩性

刚才展示的是40个节点， 如果是80个节点呢？ 经过多少轮传播才能达成一致？

大家可以自己玩一下，实际上仅仅需要4轮就可以了，

从理论上讲， Gossip协议的的复杂度是O(logN) , 如果每次随机选取4个节点作为Fanout 的话：

40个节点：  2.66 轮

80个节点：  3.16 轮

120个节点： 3.45 轮

....

可见流言蜚语协议对付节点的增长是非常有效的。

2. 容错性

假设节点A和节点B之间是有连接的，A可以向B发送消息， A-> B

突然有一天由于网络原因，A无法连接上B，消息发不过去，怎么办？

不用担心，总会有另外一个节点从另外一个路径发送给它，例如C->B

从下面的动图中能看得更加清楚， 我把两个消息传输的路径给删除了，但是对应的节点还是从其他途径收到了消息。

3. 收敛的一致性

Gossip 协议能以一传十，十传百这种指数级快速传播信息，当一个消息到达以后，能够快速传遍整个网络，系统状态的不一致可以在很快的时间内收敛，消息传播速度是log(N)

4. 极端去中心化

Gossip 协议不要求任何中心的关键节点，所有节点都可以是对等的，任何一个节点无需知道整个网络状况，只要网络是连通的，任意一个节点就可以把消息散播到全网。

其他通信模式

这个模拟器展示的只是一种通信模式： Push ， 也就是说一个节点把数据推送给其他节点。

还有拉的方式（Pull）： 节点A 将本地数据的版本告诉其他节点，其他节点将比A新的数据发给节点A,  A再来更新数据。

当然还可以有推拉结合(Push-Pull）结合的方式。

04 缺点 

世界上没有免费的午餐，流言蜚语协议也有弱点：

消息是有延迟的

Gossip协议虽然传播得很快，但是还需要经过几个轮次的传播才能到达全网的所有节点， 这就不适合对实时性要求很高的场景了。 或者说，Gossip协议只能达到最终一致性。

消息是有冗余的

从动图中可以清楚地看出，消息的发送是有冗余的，尤其是到了后面几轮，大多数节点已经收到了消息，但是还在持续选择节点发送，消息数可以说是蔚为壮观啊。

热文推荐主宰这个世界的10大算法Android开发架构思考及经验总结推荐阅读

这里有你需要的编程技术、心得、经验（数据结构与算法、源码分析等），这里不止限于技术！还有职场心得、生活感悟、以及面经等。关注公众号，第一时间送达！

看完本文有收获？请转发分享给更多人
关注「程序员小乐」，收看更多精彩内容